package LeetCode._02算法基础.day19位运算;

/**
 * @author 挚爱之夕
 * @version 中等
 * @implSpec 给你两个整数 left 和 right ，表示区间 [left, right] ，
 * 返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
 * 输入：left = 5, right = 7
 * 输出：4
 * @since 2022 - 09 - 15 - 9:52
 */
public class _201数字范围按位与 {
    public static void main(String[] args) {
        int left = 5, right = 7;
        System.out.println(rangeBitwiseAnd2(5, 7));
    }
    //超时
    public static int rangeBitwiseAnd(int left, int right) {
        int res = left;
        for(int i = left + 1; i <= right; i++) res &= i;
        return res;
    }
    /* 实际范围的按位与 只与两端的数有关 求两数二进制公共前缀 */
    //
    public static int rangeBitwiseAnd1(int left, int right) {
        int shift = 0;
        while(right > left){
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }

    //Brian Kernighan 算法 ： 消除低位的 1
    public static int rangeBitwiseAnd2(int left, int right) {
        while(right > left){
            right &= (right - 1);
        }
        return right;
    }
}
